﻿using System;
using System.Collections.Generic;
using System.Text;

namespace MisprintTestingTool
{
    enum LevenshteinMisprintType
    {
        Delete,
        Insert,
        Substitute
    }

    class LevenshteinMisprintChar
    {
        public char Char;
        public int Position;
    }

    class LevenshteinMisprint
    {
        public List<LevenshteinMisprintChar> MisprintChars;
        public LevenshteinMisprintType Type;
    }

    class LevenshteinMisprintInfo
    {
        public List<LevenshteinMisprint> Misprints = new List<LevenshteinMisprint>();
        public int Coefficient;
    }

    static class LevenshteinDistance
    {
        /// <summary>
        /// Compute the distance between two strings.
        /// </summary>
        public static int Compute(string s, string t, out List<LevenshteinMisprint> misprints)
        {
            misprints = new List<LevenshteinMisprint>();

            int n = s.Length;
            int m = t.Length;
            LevenshteinMisprintInfo[,] d = new LevenshteinMisprintInfo[n + 1, m + 1];

            if (m == 0)
            {
                int i = 0;
                foreach (char ch in s.ToCharArray())
                    misprints.Add(new LevenshteinMisprint()
                    { 
                        Type = LevenshteinMisprintType.Delete,
                        MisprintChars = new List<LevenshteinMisprintChar>() 
                        { 
                            new LevenshteinMisprintChar() 
                            { 
                                Char = ch, 
                                Position = i++ 
                            } 
                        }
                    });
                return n;
            }

            if (n == 0)
            {
                int i = 0;
                foreach (char ch in t.ToCharArray())
                    misprints.Add(new LevenshteinMisprint()
                    {
                        Type = LevenshteinMisprintType.Insert,
                        MisprintChars = new List<LevenshteinMisprintChar>() 
                        { 
                            new LevenshteinMisprintChar() 
                            { 
                                Char = ch, 
                                Position = i++ 
                            } 
                        }
                    });
                return m;
            }

            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= m; j++)
                {
                    d[i, j] = new LevenshteinMisprintInfo()
                    {
                        Coefficient = 0
                    };
                }
            }

            for (int i = 0; i <= n; i++)
            {
                d[i, 0] = new LevenshteinMisprintInfo()
                {
                    Coefficient = i
                };
            }

            for (int j = 0; j <= m; j++)
            {
                d[0, j] = new LevenshteinMisprintInfo()
                {
                    Coefficient = j
                };
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                    int delete = d[i - 1, j].Coefficient + 1;
                    int insert = d[i, j - 1].Coefficient + 1;
                    int substitution = d[i - 1, j - 1].Coefficient + cost;

                    d[i, j].Coefficient = Math.Min(Math.Min(delete, insert), substitution);

                    if (d[i, j].Coefficient == substitution)
                    {
                        d[i, j].Misprints = new List<LevenshteinMisprint>(d[i - 1, j - 1].Misprints);

                        if (cost != 0)
                            d[i, j].Misprints.Add(new LevenshteinMisprint()
                            {
                                Type = LevenshteinMisprintType.Substitute,
                                MisprintChars = new List<LevenshteinMisprintChar>()
                                { 
                                    new LevenshteinMisprintChar() { Char = s[i - 1], Position = i - 1 }, 
                                    new LevenshteinMisprintChar() { Char = t[j - 1], Position = j - 1 }
                                }
                            });
                    }
                    else if (d[i, j].Coefficient == insert)
                    {
                        d[i, j].Misprints = new List<LevenshteinMisprint>(d[i, j - 1].Misprints);
                        d[i, j].Misprints.Add(new LevenshteinMisprint()
                        {
                            Type = LevenshteinMisprintType.Insert,
                            MisprintChars = new List<LevenshteinMisprintChar>()
                            {
                                new LevenshteinMisprintChar() { Char = t[j - 1], Position = j - 1 } 
                            }
                        });
                    }
                    else if (d[i, j].Coefficient == delete)
                    {
                        d[i, j].Misprints = new List<LevenshteinMisprint>(d[i - 1, j].Misprints);
                        d[i, j].Misprints.Add(new LevenshteinMisprint()
                        {
                            Type = LevenshteinMisprintType.Delete,
                            MisprintChars = new List<LevenshteinMisprintChar>()
                            { 
                                new LevenshteinMisprintChar() { Char = s[i - 1], Position = i - 1 } 
                            }
                        });
                    }

                    if (d[i, j].Misprints.Count == 0 && d[i, j].Coefficient != 0)
                    {
                        for (int x = 0; x < d[i, j].Coefficient; x++)
                        {
                            d[i, j].Misprints.Add(new LevenshteinMisprint()
                            {
                                Type = d[i, j].Coefficient <= t.Length ? LevenshteinMisprintType.Insert : LevenshteinMisprintType.Delete,
                                MisprintChars = new List<LevenshteinMisprintChar>()
                                { 
                                    new LevenshteinMisprintChar() { Char = d[i, j].Coefficient <= t.Length ? t[x] : s[x], Position = x } 
                                }
                            });
                        }
                    }
                }
            }

            misprints = d[n, m].Misprints;

            return d[n, m].Coefficient;
        }
    }
}
